/*
 * @lc app=leetcode.cn id=421 lang=csharp
 *
 * [421] 数组中两个数的最大异或值
 */

// @lc code=start
public class Solution {
    public int FindMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        for (int i = 31; i >= 0; i--) {
            mask |= (1 << i); // 依次将mask第i位置1
            HashSet<int> set = new HashSet<int>();
            foreach (int num in nums) {
                set.Add(num & mask); // 取前缀
            } 
            int tmp = max | (1 << i); // 假设答案第i位可以取到1
            foreach (int prefix in set) {
                if (set.Contains(tmp ^ prefix)) { // tmp = prefix ^ other, tmp ^ prefix = other
                    max = tmp; // 第i位为1成立
                    break;
                }
            }
        }
        return max;
    }
}
// @lc code=end

